The invention relates generally to a positioning technique in which a target device's location is estimated on the basis of a sequence of observations on the target device's wireless communication environment. FIG. 1 schematically illustrates an example of such a positioning technique. A target device T communicates via base stations BS via a radio interface RI. In this example, the communication is assumed to be radio communication. The target device T observes signal values at the radio interface RI. The observations O are applied to a probabilistic model PM that models the target device's wireless communication environment and produces a location estimate LE. As used herein, a target device is a device whose location is to be determined. The target device communicates via signals in a wireless environment, and signal values in the wireless environment are used for determining the target device's location. For example, the target device may be a data processing device communicating in a wireless local-area network (WLAN). The data processing device may be a general-purpose laptop or palmtop computer or a communication device, or it may be a dedicated test or measurement apparatus such as a hospital instrument connected to the WLAN. A location, as used herein, is a coordinate set of one to three coordinates. In some special cases, such as tunnels, a single coordinate may be sufficient but in most cases the location is expressed by a coordinate pair (x, y or angle/radius).
More particularly, the invention relates to a positioning technique that is based on a Hidden Markov Model. FIG. 2 schematically illustrates a Hidden Markov Model HMM. The model consists of locations, transitions between the locations and observations made at the locations. In the example shown in FIG. 2, the target device moves along a path of which five locations qt−2 through qt+2 are shown. More formally, qt defines the location distribution at time t, so that P(qt=s) is the probability for the target device being at location s at time t. However, because a location distribution can easily be converted to a single location estimate, the shorthand notation “location q” will be used to refer to a location distribution q.
The locations along the target device's path can be called path points. The target device communicates via signals in a wireless environment, and signal values in the wireless environment are used for determining the target device's location.
A practical example of the target device is a data processing device communicating in a wireless local-area network (WLAN) or a cellular radio network. The data processing device may be a general-purpose laptop or palmtop computer or a communication device, or it may be a dedicated test or measurement apparatus such as a hospital instrument connected to the WLAN. A signal value, as used herein, is a measurable and location-dependent quantity of a fixed transmitter's signal. For example, signal strength and bit error rate/ratio are examples or measurable and location-dependent quantities.
The word ‘hidden’ in the Hidden Markov Model stems from the fact that we are primarily interested in the locations qt−2 through qt+2 but the locations are not directly observable. Instead we can make a series of observations ot−2 through ot+2 on the basis of the signal values but there is no simple relationship between the observations ot−2 . . . ot+2 and locations qt−2 . . . qt+2. (Note that the straight arrows through the locations qt−2 through qt+2 are not meant to imply that the target devices moves along a straight path or with a constant speed, or that the observations are made at equal intervals.)
Note that a single ‘observation’ may comprise, and typically does comprise, several signal value measurements from one or more channels. In a probabilistic model, the idea is to measure the probability distribution of a signal value, and if there is any overlap in signal values in various locations, the locations cannot be determined on the basis of a single measurement per location. Instead, each observation must comprise a plurality of measurements in order to determine a probability distribution.
It should also be understood that in FIGS. 1 and 2, time is quantified. This means that a target device that has a single radio receiver may only observe one channel at any point of time, but the radio receiver can be re-tuned to a different channel in milliseconds, whereas the observations ot−2 . . . ot+2 are typically separated by at least a hundred milliseconds. The interval between observations can be selected based on the a typical target device's speed. Thus a single observation can comprise signal values from several channels even if a radio receiver has to be re-tuned between channels.
The radio receiver may measure signal values, such as signal strength, virtually continuously, but in a positioning application based on a Hidden Markov Model, it is beneficial to treat the observations in quantified time. Thus the term ‘observation’ can be summarized as a statistical sample of several signal values from a given period of time.
A problem underlying the invention derives from the Hidden Markov Model: we cannot observe a variable that has a monotonous relationship with distance or location. Instead the positioning method is based on observations of signal values. It is possible for two or more locations to have near-identical sets of signal values, and a location estimate may be grossly inaccurate.